package dateStructure;

import java.util.Scanner;

public class character {
    public static void main(String arg[]) {
        Scanner scanner = new Scanner(System.in);
        String s, f;
        System.out.print("请输入第一个字符串：");
        s = scanner.nextLine();
        System.out.print("请输入第二个字符串：");
        f = scanner.nextLine();
        System.out.println("f字符在s字符中第一次匹配到的字符下标为：" + index_BF(s, f));
    }

    public static int index_BF(String s, String f) {
        int i = 0;//这是s字符的下标索引
        int j = 0;//这是s字符的下标索引
        int sum = 0;//这是字符比较的总次数
        int len1 = s.length();//这是s字符串的长度
        int len2 = f.length();//这是f字符串的长度
        while (i < len1 && j < len2) {//开始进行比较
            if (s.toCharArray()[i] == f.toCharArray()[j]) {//发现对应索引下的字符相同了
                i++;
                j++;
                //s f字符对应索引相应+1
            } else {//一旦出现不相同的了
                //i-=(j-1);//快速写法
                i = i - j + 1;//i就回到i-j+1这个索引下标去
                j = 0;//在Java中是回到0索引下
            }
            sum++;
        }
        System.out.println("s字符串与f字符串比较的总次数为：" + sum);
        //判断j索引是否在退出while循环后，走到了最后面，即f字符串长度的那个位置
        //如果不是则返回-1，表示在s字符串中没有匹配到f字符串
        return j == len2 ? i - len2 : -1;
    }
}

class character1 {
    //kmp算法
    public static void main(String arg[]) {
        Scanner scanner = new Scanner(System.in);
        String s, f;
        //abaabaabeca
        //abaabe
        s = scanner.nextLine();
        System.out.println("第一个字符串s为："+s);
        f = scanner.nextLine();
        System.out.println("第二个字符串s为："+f);
        System.out.println("kmp算法找到字符串第一次匹配的下标为：" + kmp(s.toCharArray(), f.toCharArray()));
    }

    private static int[] getNext(char t[]) {
        int len = t.length;//这个为字符串t的长度
        int next[] = new int[len];//开一个字符串长度为t的字符
        int j = 0;//j初始化为0，Java从0开始
        int k = -1;//k初始化为-1
        next[0]=-1;//next数组第一个初始化为-1
        while (j < len - 1) {//len-1的原因是为了防止最后j+1的时候越界了
            if (k == -1 || t[j] == t[k]) {//如果k=-1即还在初始位置的话，或者j下标和k下标下的字符匹配相同的话
                next[++j] = ++k;
                //改进版
                if(t[j]==t[k]){
                    next[j]=next[k];
                }
            }
            else{
                k = next[k];//如果匹配不相同的话，就把k下标回溯到next[k]的位置
            }
        }
        return next;
    }

    /**
     *
     * @param s 字符串原串
     * @param f 字符串匹配串
     * @return s字符串中f字符串第一次出现的位置下标
     */
    private static int kmp(char s[], char f[]) {
        int next[] = getNext(f);
        int i = 0;//i表示字符串s的下标，从0开始
        int j = 0;//j表示字符串f的下标，从0开始
        int len1 = s.length;//len1表示字符串s的长度
        int len2 = f.length;//len2表示字符串f的长度
        int sum = 0;//这是字符比较的总次数
        while (i < len1 && j < len2) {
            if (j==-1||s[i] == f[j]) {//j仍等于-1即刚开始位置，或者发现对应索引下的字符相同了
                i++;
                j++;
                //s f字符对应索引相应+1
            } else {
                j = next[j];//如果匹配到不想等了，就对j进行回溯
            }
            sum++;
        }
        System.out.println("s字符串与f字符串比较的总次数为：" + sum);
        //判断j索引是否在退出while循环后，走到了最后面，即f字符串长度的那个位置
        //如果不是则返回-1，表示在s字符串中没有匹配到f字符串
        return j == len2 ? i - len2 : -1;
    }
}

class character2 {
    //病毒检测
    public static void main(String arg[]) {
        //eabbacab
        Scanner scanner = new Scanner(System.in);
        String s, f;
        s = scanner.nextLine();
        System.out.println("该人的DNA序列为“：" + s);
        f = scanner.nextLine();
        System.out.println("病毒的DNA序列为：" + f);
        if (virusJudge(s.toCharArray(), f.toCharArray())) {
            System.out.println("该人已患病毒！");
        } else {
            System.out.println("该人健康。");
        }
    }

    /**
     *
     * @param t 匹配的字符串
     * @return next数组
     */
    private static int[] getNext(char t[]) {
        int len = t.length;//len代表字符串t的长度
        int next[] = new int[len];//定义一个空间长度为字符串t长度的next数组
        int j = 0;
        int k = -1;//k作为回溯的下标从-1开始
        next[0]=-1;
        while (j < len - 1) {//len-1是为了防止++j越界了
            if (k == -1 || t[j] == t[k]) {//如果k退到最前面了=-1，或者两个字符相等
                next[++j] = ++k;
                //改进版
                if (t[j] == t[k]) {
                    next[j] = next[k];
                }
            } else {
                k = next[k];
            }
        }
        return next;
    }

    /**
     * @param s 人类DNA序列
     * @param f 病毒DNA序列
     * @return 两者DNA是否有匹配到
     */
    private static int kmp(char s[], char f[]) {
        int len1 = s.length;//代表字符串s的长度
        int len2 = f.length;//代表字符串f的长度
        int next[] = getNext(f);
        int i = 0;
        int j = -1;
        while (i < len1 && j < len2) {
            if (j == -1 || s[i] == f[j]) {//如果j回退到了最前面，或者当前索引下的字符相同的话
                i++;
                j++;
            } else {//如果索引下的字符不相同的话，开始回退
                j = next[j];
            }
        }
        return j == len2 ? i - len2 : -1;//如果j和len2相等了，说明字符串已经匹配成功,如果不成功返回-1
    }

    /**
     * @param s 人类的DNA
     * @param f 　病毒的DNA
     *          　@return　该人是否被感染
     */
    private static boolean virusJudge(char s[], char f[]) {
        int len = f.length;//len2代表病毒的长度
        char t[] = new char[len << 1];//开一个空间长度为病毒DNA长度两倍的字符串t
        char temp[] = new char[len];//开一个临时数组装病毒的各种序列
        for (int i = 0; i < len; i++) {
            t[i] = f[i];//把病毒序列放入到其两倍长的数组的前一部分
            t[i+ len] = f[i];//同样，吧病毒序列放到其两倍长的数组的后一部分
        }
        for (int i = 0; i < len; i++) {
            /**样例aabb病毒序列的四种序列
             * aabb
             * abba
             * bbaa
             * baab
             */
            for (int j = 0; j < len; j++) {
                temp[j] = t[i + j];//通过控制其索引号把病毒的四种不同序列放到临时数组中去
            }
            if (kmp(s, temp) != -1) {//开始比较判断，如果返回值不为-1，则匹配到人体中有病毒
                return true;
            }
        }
        return false;
    }
}
